/** 
 * UIMA Annotation Mapper
 * Copyright (C) 2010  Nicolas Hernandez
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *     http://www.apache.org/licenses/LICENSE-2.0
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package fr.univnantes.lina.uima.mapper.annotation.located;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import org.apache.uima.cas.Type;
import org.apache.uima.cas.text.AnnotationFS;
import org.apache.uima.cas.text.AnnotationIndex;
import org.apache.uima.jcas.JCas;
import org.apache.uima.jcas.tcas.Annotation;

import fr.univnantes.lina.uima.common.JCasSofaViewUtils;

/**
 * Warning: the next and the previous offset depend on the closest annotation (respectively following and preceding). 
 * If that one stands for whitespace than a process of filtering should be set up (during the first pass of AnnotationIndex)
 * 
 * @author hernandez
 *
 */
public class LocatedAnnotationIndexBuilder {

	/**
	 * Builds a LocatedAnnotationIndex from an AnnotationIndex
	 * input aJCas.getAnnotationIndex() ou bien  aJCas.getFSIndexRepository()
	 * @param aJCas containing an AnnotationIndex
	 * @return a build locatedAnnotationIndex from the AnnotationIndex 
	 */
	public static LocatedAnnotationIndex buildsIndex (JCas aJCas) {

		// --------------------------------------------------------------------
		// Initialize the index structures
		LocatedAnnotationIndex locatedAnnotationIndex = new LocatedAnnotationIndex();
		Map<String,LocatedAnnotation> locatedAnnotationMap = locatedAnnotationIndex.getLocatedAnnotationMap();
		Map<Integer,List<Annotation>> annotationBeginMap = locatedAnnotationIndex.getAnnotationBeginMap();
		Map<Integer,List<Annotation>> annotationEndMap = locatedAnnotationIndex.getAnnotationEndMap();
		int annotationMinBegin = 0;
		int annotationMaxEnd = 0;

		// --------------------------------------------------------------------
		// FIRST PASS of the AnnotationIndex :  
		// builds locatedAnnotationMap LocatedAnnotation current 
		// builds annotationBeginMap
		// builds annotationEndMap
		AnnotationIndex<Annotation> annotationIndex = null;

		Iterator<Annotation> annotationIndexIterator = null;
		annotationIndex = (AnnotationIndex<Annotation>) aJCas.getAnnotationIndex();
		annotationIndexIterator = annotationIndex
				.iterator();

		// --------------------------------------------------------------------
		while (annotationIndexIterator.hasNext()) {
			// ----------------------------------------------------------------
			// the current annotation
			Annotation annotation = null;
			annotation = (Annotation) annotationIndexIterator
					.next();
			String annotationOffset = Offset.getOffset(annotation);
			int annotationBegin = annotation.getBegin();
			int annotationEnd = annotation.getEnd();
			//System.out.println("Debug: annotation.getType().getName() >"+annotation.getType().getName()+"< ");

			// ---------------------------------------------------------------- 
			// add the annotation to the current set of the locatedAnnotation of locatedAnnotationMap at this offset
			List<Annotation> currentAnnotationList = null;
			LocatedAnnotation locatedAnnotation = null; 
			if (locatedAnnotationMap.containsKey(annotationOffset)) {
				//System.out.println("Debug: locatedAnnotationMap.containsKey(annotationOffset)");
				// ASSUMPTION: means that current has already been created in the locatedAnnotation by the current loop
				locatedAnnotation = (LocatedAnnotation) locatedAnnotationMap.get(annotationOffset);
				currentAnnotationList = (List<Annotation>) locatedAnnotation.getCurrent();
			}
			else {
				//System.out.println("Debug: ! locatedAnnotationMap.containsKey(annotationOffset)");
				locatedAnnotation = new LocatedAnnotation();
				locatedAnnotation.setBegin(annotationBegin);
				locatedAnnotation.setEnd(annotationEnd);
			}

			locatedAnnotation.addCurrent(annotation);

			//locatedAnnotation.setCurrent(currentAnnotationList);
			//List<Annotation> testCurrentAnnotationList = (List<Annotation>) locatedAnnotation.getCurrent();
			//System.out.print("Debug: locatedAnnotation.getCurrent();");
			//for (Annotation testAnnotation : testCurrentAnnotationList) {
			//	System.out.print(">"+annotation.getType().getName()+"< ");
			//}
			//System.out.println("");
			// necessary ? yes 
			locatedAnnotationMap.put(annotationOffset, locatedAnnotation);

			// ----------------------------------------------------------------
			// add the annotation to the list of the annotation at this current begin
			List<Annotation> beginAnnotationList = null;
			if (annotationBeginMap.containsKey(annotationBegin)) {
				beginAnnotationList = (List<Annotation>) annotationBeginMap.get(annotationBegin);
			}
			else {
				beginAnnotationList = new ArrayList<Annotation> ();
			}
			beginAnnotationList.add(annotation);
			// necessary ? yes
			annotationBeginMap.put(annotationBegin, beginAnnotationList);

			// ----------------------------------------------------------------
			// add the annotation to the list of the annotation at this current end
			List<Annotation> endAnnotationList = null;
			if (annotationEndMap.containsKey(annotationEnd)) {
				endAnnotationList = (List<Annotation>) annotationEndMap.get(annotationEnd);
			}
			else {
				endAnnotationList = new ArrayList<Annotation> ();
			}
			endAnnotationList.add(annotation);
			// necessary ? yes
			annotationEndMap.put(annotationEnd, endAnnotationList);

		}
		// necessary ? no 
		// locatedAnnotationIndex.setLocatedAnnotationMap(locatedAnnotationMap);
		// necessary ? no 
		//locatedAnnotationIndex.setAnnotationBeginMap(annotationBeginMap);
		// necessary ? no 
		//locatedAnnotationIndex.setAnnotationEndMap(annotationEndMap);

		// --------------------------------------------------------------------
		// FIRST PASS of the LocatedAnnotationIndex :  
		// builds locatedAnnotationMap LocatedAnnotation next, previous and partial 
		// initialize minBegin and maxEnd

		TreeMap<Integer,List<Annotation>> annotationBeginSortedMap = new TreeMap(locatedAnnotationIndex.getAnnotationBeginMap());
		TreeMap<Integer,List<Annotation>> annotationEndSortedMap = new TreeMap(locatedAnnotationIndex.getAnnotationEndMap());
		Set<Integer> beginSortedSet = annotationBeginSortedMap.keySet();
		Set<Integer> endSortedSet = annotationEndSortedMap.keySet();


		Set<String> offsetSet = locatedAnnotationMap.keySet();

		for (String annotationOffset : offsetSet) {
			//System.out.print("Debug: offset>"+annotationOffset+"< "); 
			LocatedAnnotation locatedAnnotation = (LocatedAnnotation) locatedAnnotationMap.get(annotationOffset);
			int begin = locatedAnnotation.getBegin();
			int end = locatedAnnotation.getEnd();

			// annotationMinBegin will always be 0 so does not need for computing
			//annotationMinBegin = Math.min(annotationMinBegin, begin);
			annotationMaxEnd = Math.max(annotationMaxEnd, end);

			// where starts the begin of the next locatedAnnotation ? 
			// it is such that it should be a begin of an annotation strictly superior to the end the locatetAnnotation and in the same time the nearest
			// in other words in the sorted keys of the annotation begin map, it is the least key strictly greater than the end of the given locatedAnnotation, or null if there is no such element.

			if (annotationBeginSortedMap.higherKey(end) != null) {
				int nextBegin = annotationBeginSortedMap.higherKey(end);
				// what are the annotations of the next locatedAnnotation ?
				// they are the list of annotation referenced by the next begin key in the annotationBeginSortedMap
				locatedAnnotation.addNext(annotationBeginSortedMap.get(nextBegin));
				locatedAnnotationMap.put(annotationOffset, locatedAnnotation);
			}

			// where does the end of the previous locatedAnnotation finish ?
			// it is such that it should be an end of an annotation strictly inferior to the begin the locatedAnnotation and in the same time the nearest
			// in other words in the sorted keys of the annotation end map, it is the greatest key strictly less than the begin of the given locatedAnnotation, or null if there is no such element.
			if (annotationEndSortedMap.lowerKey(begin) != null) {
				int previousEnd = annotationEndSortedMap.lowerKey(begin);
				// what are the annotations of the next locatedAnnotation ?
				// they are the list of annotation referenced by the next begin key in the annotationBeginSortedMap
				locatedAnnotation.addPrevious(annotationEndSortedMap.get(previousEnd));
				locatedAnnotationMap.put(annotationOffset, locatedAnnotation);
			}

			// partialNext
			// PRECOND (partialNext.begin > current.begin)  && (partialNext.begin < current.end) && (partialNext.end > current.end)
			// all the annotation referenced in  annotationBeginSortedMap starting from the first one following in annotationBeginSortedMap and ending when > current.end which respects the PRECOND (partialNext.end > current.end)
			// TODO

			// partialPrevious
			// TODO

		}

		// --------------------------------------------------------------------
		// Second PASS of the LocatedAnnotationIndex :  
		// builds locatedAnnotationMap LocatedAnnotation super and sub

		// Need for a top LocatedAnnotation parent for all locatedAnnotations
		LocatedAnnotation topLocatedAnnotation = new LocatedAnnotation();
		topLocatedAnnotation.setBegin(annotationMinBegin);
		topLocatedAnnotation.setEnd(annotationMaxEnd);



		// we browse the sorted begin offset and not the locatedAnnotationMap key offsets 
		// since this order (begin ascending and end descending) is an ASSUMPTION
		// but we work in practice with the corresponding located annotation 
		// but since some annotations have similar offset we should filter the duplicate
		Map<String,Integer> offsetAlreadySeen = new HashMap<String, Integer>();
		for (int begin : beginSortedSet) {
			List<Annotation> offsetAnnotationList = annotationBeginMap.get(begin);

			for (Annotation annotation : offsetAnnotationList) {
				//System.out.println("\tbegin>"+annotation.getBegin()+"< end>"+annotation.getEnd()+"< >"+annotation.getType().getName()+"< ");


				if (! offsetAlreadySeen.containsKey((Offset.getOffset(annotation)))) {
					// we do not proceed twice the same offset 
					offsetAlreadySeen.put(Offset.getOffset(annotation),1);

					searchParent (locatedAnnotationMap, Offset.getOffset(topLocatedAnnotation), Offset.getOffset(annotation), false);
				}
			}
		}

		// --------------------------------------------------------------------
		// on parcours une à une les annotations de l'AnnotationIndex
		// pour chacune on regarde si il existe une LocatedAnnotation
		// si non on la crée
		// on ajoute l'annotation dans current (il n y a pas à vérifier l'existence de doublon, forcément c'est la 1ère fois qu'on la rencontre dans l'annotationIndex)
		// on parcours une à une les LocatedAnnotation créées 
		// pour chacune on parcours l AnnotationIndex 
		// si différent offset  
		// alors si l 'annotation courante super 
		// 		alors on l'ajoute dans super
		// idem pour sub
		// pour partial il faut qu'une seule soit comprise 
		// pour strict next et previous c'est plus compliqué... sauf si on suppose que next ou previous est à 1 white char... ... il faut faire appel à beginMap et endMap...
		// ca reste toujours très lourd n * n ... alors qu'en pratique on sait que peu de next ou previous 

		return locatedAnnotationIndex;
	}



	/**
	 * Search recursively the focus locatedAnnotation where to add the current locatedAnnotation
	 * Based on sorted begin offset map (ascending begin and descending end) with no duplicate
	 * @param treeFocusOffset
	 * @param currentOffset
	 * @param found
	 * @return true if found
	 */
	private static boolean searchParent (Map<String,LocatedAnnotation> locatedAnnotationMap, String treeFocusOffset, String currentOffset, boolean found) {


		if (subsumeLoosely(locatedAnnotationMap.get(currentOffset),locatedAnnotationMap.get(treeFocusOffset))) {
			List<Annotation> childAnnotationList = locatedAnnotationMap.get(treeFocusOffset).getSub();
			Iterator childAnnotationListIterator = childAnnotationList.iterator();
			while (childAnnotationListIterator.hasNext() && (!found)) {
				Annotation annotationChild = (Annotation) childAnnotationListIterator.next();
				found = searchParent (locatedAnnotationMap,Offset.getOffset(annotationChild), currentOffset, found);
			}
			if (! found) {
				// no child is subsumed or no child at all (which is the case for topLocatedAnnotation)
				// children do not hold subsumption relation

				// add sub (e.g. a sentence annotation may cover several word annotations) 
				// and set super (since current does not have any super we set it we do not add it)
				locatedAnnotationMap.get(treeFocusOffset).addSub(locatedAnnotationMap.get(currentOffset).getCurrent());
				locatedAnnotationMap.get(currentOffset).setSuper(locatedAnnotationMap.get(treeFocusOffset).getCurrent());

				// necessary ? yes
				locatedAnnotationMap.put(treeFocusOffset, locatedAnnotationMap.get(treeFocusOffset));
				// necessary ? yes
				locatedAnnotationMap.put(currentOffset, locatedAnnotationMap.get(currentOffset));
			}
			return true;
		}
		else if (subsumeStrictly(locatedAnnotationMap.get(treeFocusOffset),locatedAnnotationMap.get(currentOffset))) {
			// set sub and super 
			locatedAnnotationMap.get(currentOffset).setSuper(locatedAnnotationMap.get(treeFocusOffset).getSuper());
			locatedAnnotationMap.get(currentOffset).setSub(locatedAnnotationMap.get(treeFocusOffset).getCurrent());
			locatedAnnotationMap.get(treeFocusOffset).setSuper(locatedAnnotationMap.get(currentOffset).getCurrent());

			// necessary ? yes
			locatedAnnotationMap.put(treeFocusOffset, locatedAnnotationMap.get(treeFocusOffset));
			// necessary ? yes
			locatedAnnotationMap.put(currentOffset, locatedAnnotationMap.get(currentOffset));
			return true;
		} 
		//else {
		return false;	
		//}
	}


	/**
	 * Test if a is included in b
	 * @param treeFocus
	 * @param current
	 * @return
	 */
	private static boolean subsumeStrictly (LocatedAnnotation a, LocatedAnnotation b) {
		return (a.getBegin() > b.getBegin() &&  a.getEnd() < b.getEnd())  ;
	}
	/**
	 * Test if a is included in b
	 * @param treeFocus
	 * @param current
	 * @return
	 */
	private static boolean subsumeLoosely(LocatedAnnotation a, LocatedAnnotation b) {
		return (a.getBegin() > b.getBegin() &&  a.getEnd() < b.getEnd()) 
				|| (a.getBegin() == b.getBegin() &&  a.getEnd() < b.getEnd()) 
				|| (a.getBegin() > b.getBegin() &&  a.getEnd() == b.getEnd()) ;
	}
}
